# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 快速排序
# 基本思想: 从数列中挑出一个元素，称为"基准"(pivot), 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
# （相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
# 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

# 时间复杂度:最坏O(n^2),平均O(nlogn),n越大，速度越快
# 空间复杂度: 最好O(logn)(每次分割都平均分),最坏O(n)(每次分割都分割一个子序列和一个空序列),平均O(logn)
# 稳定性：不稳定
from arr_util import random_scale_arr


def quick_sort(num_arr):
    quick_func(num_arr, 0, len(num_arr) - 1)


def quick_func(num_arr, low, high):
    if low < high:
        pivot = partition(num_arr, low, high)
        quick_func(num_arr, low, pivot)
        quick_func(num_arr, pivot + 1, high)


# partition函数，实现三数中值分割法
def partition(num_arr, low, high):
    # 选取第一个元素为枢轴记录
    pivot = num_arr[low]
    while low < high:
        # 将比枢轴记录小的交换到低端
        while low < high and num_arr[high] >= pivot:
            high -= 1
        num_arr[low] = num_arr[high]

        while low < high and num_arr[low] <= pivot:
            low += 1
        # 将比枢轴记录大的交换到高端
        num_arr[high] = num_arr[low]
    # 枢纽所在位置赋值
    num_arr[low] = pivot
    return low


if __name__ == '__main__':
    arr = [4, 1, 3, 2, 7]
    quick_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    quick_sort(arr2)
    print(arr2)

